The Viterbi algorithm, developed by Andrew J. Viterbi, has been widely adopted in convolutional codes for digital communication, wireless local area networks, audio and video broadcasting, and cellular telephones, among others. The Viterbi algorithm is also used for maximum likelihood sequence estimation (MLSE) for channel equalization in a wide range of digital communication receivers, digital signal demodulation, and data storage. A derivative of the basic Viterbi algorithm is called the forward and backward Viterbi algorithm, or log-Max algorithm. This is used as an approximation to the maximum a posteriori probability (MAP) algorithm to decode Turbo codes.
Considering its application for convolutional codes as an example, for a simple rate-½ convolutional code, the encoder generates two outputs, ck,1 and ck,2, at each encoding state. Typically, these two outputs ck,1 and ck,2 are equal to either 0 or 1. 0 and 1 can also be thought of as logical false and logical true or as Boolean variables. In a convolutional encoder, the logical values of ck,1 and ck,2 depend on the input at the specific time, and on the state of the finite state machine that performs the encoding operations. The state of the finite state machine depends on previous inputs to the encoder.
When a rate-½ convolutional code is decoded by a receiver, the Viterbi algorithm takes two inputs xk,1 and xk,2. Mathematically, the Viterbi algorithm compares these two inputs xk,1 and xk,2 with the encoder output of ck,1 and ck,2. The values of 2ck,1−1 and 2ck,2−1 are compared with xk,1 and xk,2 in a stage by stage fashion. The branch metric unit of the Viterbi algorithm computes four branch metric values as −xk,1−xk,2, −xk,1+xk,2, +xk,1+xk,2 for all the possible correlations between (2ck,m−1) and xk,m, m=1, 2. Computing and comparing all the possible correlations takes time and computing resources. Accordingly, the cost and delay in decoding convolutional code inhibit the use and adoption of convolutional codes and other communication techniques that may benefit from the Viterbi algorithm and other techniques that use branch metric determinations.